#include "NFA.h"
#include <queue>
using std::queue;
const vector<size_t>NE = {};

NFA::NFA()
{
    this->charset_cnt = 0;
    this->final_state = {};
    this->initial_state = {};
    this->state_cnt = 0;
    this->trans = {};
}

NFA::NFA(size_t sc, size_t cc, map<pair<size_t, vector<size_t>>, set<size_t>> t, set<size_t> is, set<size_t> fs)
{
    this->state_cnt = sc;
    this->charset_cnt = cc;
    this->trans = t;
    this->initial_state = is;
    this->final_state = fs;
}

set<size_t> NFA::closure(set<size_t> I) 
{
    queue<size_t>que;
    for (const auto& i : I)
        que.push(i);
    while (que.size())
    {
        size_t i = que.front();
        que.pop();
        for (const auto& s : this->trans[make_pair(i, NE)])
        {
            if (I.count(s))continue;
            I.insert(s);
            que.push(s);
        }
    }
    return I;
}

set<size_t> NFA::go(set<size_t> I, size_t a)
{
    set<size_t>ret;
    for (const auto& i : I)
    {
        const set<size_t> s = this->trans[make_pair(i, vector<size_t>({ a }))];
        for (const auto& j : s)
            ret.insert(j);
    }
    return ret;
}

void NtoD(const NFA * nfa, DFA* dfa)
{
    size_t state_cnt = nfa->state_cnt;
    size_t initial_state = state_cnt++;
    size_t final_state = state_cnt++;
    map<pair<size_t, vector<size_t>>, set<size_t>>trans_back = nfa->trans;
    for (auto& i : nfa->initial_state)
        trans_back[std::make_pair(initial_state, NE)].insert(i);
    for (auto& i : nfa->final_state)
        trans_back[std::make_pair(i, NE)].insert(final_state);
    map<pair<size_t, vector<size_t>>, set<size_t>>trans;
    for (auto& i : trans_back)
    {
        if (i.first.second.size() > 1)
        {
            size_t current_state = i.first.first;
            for (auto& j : i.first.second)
            {
                size_t tmp_state = state_cnt++;
                trans[std::make_pair(current_state, vector<size_t>({ j }))].insert(tmp_state);
                current_state = tmp_state;
            }
            trans[std::make_pair(current_state, NE)] = i.second;
        }
        else
            trans[i.first] = i.second;
    }
    trans_back = {};
    NFA n_nfa = NFA(state_cnt, nfa->charset_cnt, trans, { initial_state }, { final_state });
    map<set<size_t>, size_t>mp;
    vector<set<size_t>>mp2;
    queue<size_t>que;
    set<size_t>s = n_nfa.closure({ initial_state });
    dfa->charset_cnt = n_nfa.charset_cnt;
    dfa->state_cnt = 0;
    mp[s] = dfa->state_cnt++;
    mp2.push_back(s);
    que.push(mp[s]);
    dfa->initial_state = 0;
    while (que.size())
    {
        size_t l = que.front();
        que.pop();
        for (size_t i = 0; i < n_nfa.charset_cnt; i++)
        {
            set<size_t>tmp = n_nfa.closure(n_nfa.go(mp2[l], i));
            if (tmp.empty())continue;
            size_t tmp_id;
            if (!mp.count(tmp))
            {
                mp[tmp] = tmp_id = dfa->state_cnt++;
                mp2.push_back(tmp);
                if (tmp.count(final_state))
                    dfa->final_state.insert(tmp_id);
                que.push(tmp_id);
            }
            else
                tmp_id = mp[tmp];
            dfa->trans[std::make_pair(l, i)] = tmp_id;
        }
    }
    return;
}


